/* ****************************************************************************
 *
 * Copyright (c) Microsoft Corporation. 
 *
 * This source code is subject to terms and conditions of the Microsoft Public License. A 
 * copy of the license can be found in the License.html file at the root of this distribution. If 
 * you cannot locate the  Microsoft Public License, please send an email to 
 * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound 
 * by the terms of the Microsoft Public License.
 *
 * You must not remove this notice, or any other, from this software.
 *
 *
 * ***************************************************************************/

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics;
using Microsoft.Scripting.Generation;
using Microsoft.Scripting.Runtime;
using Microsoft.Scripting.Utils;

namespace Microsoft.Scripting.Ast {
    /// <summary>
    /// ScopeInfo is the data structure which the Compiler keeps information
    /// related to compiling scopes. It stores the following information:
    ///   1. Parent relationship (for resolving variables)
    ///   2. Information about lifted variables
    ///   3. Information for resolving closures
    /// 
    /// Instances are produced by VariableBinder, which does a tree walk
    /// looking for scope nodes: LambdaExpression, GeneratorLambdaExpression,
    /// and ScopeExpression.
    /// </summary>
    internal sealed partial class ScopeInfo {
        // parent scope, if any
        private readonly ScopeInfo _parent;
        
        // the expression node for this scope
        private readonly Expression _expression;

        // does this scope (or any inner scope) close over variables from any parent scope?
        private readonly bool _isClosure;

        // does this scope (or any inner scope in this generator) contain a yield?
        private readonly bool _scopeHasYield;

        // The scope's environment, if any.
        // provides storage for variables that are lifted (referenced from nested lambdas)
        private readonly EnvironmentInfo _environment;

        // variables defined in this scope but not lifted
        private readonly ReadOnlyCollection<Expression> _localVars;

        // Mutable dictionary that maps environments to IL locals
        // Shared by all scopes within the same lambda
        private readonly Dictionary<EnvironmentInfo, Slot> _closureAccess;

        // Mutable dictionary that maps non-lifted variables to either local
        // slots or argument slots
        private readonly Dictionary<Expression, Slot> _localSlots = new Dictionary<Expression, Slot>();

        internal ScopeInfo(
            ScopeInfo parent,
            Expression expression,
            bool isClosure,
            bool scopeHasYield,
            ReadOnlyCollection<Expression> liftedVars,
            ReadOnlyCollection<Expression> localVars
        ) {
            Assert.NotNull(expression, liftedVars, localVars);

            _isClosure = isClosure;
            _scopeHasYield = scopeHasYield;
            _parent = parent;
            _expression = expression;
            _localVars = localVars;

            Debug.Assert(!_scopeHasYield || IsScopeExpression); // only scopes track yielding

            // only generators have two ScopeInfos pointing at the same expression
            // same_parent_expression implies is_generator
            Debug.Assert(_parent == null || _parent.Expression != _expression || _expression.NodeType == ExpressionType.Generator);

            if (liftedVars.Count > 0) {
                _environment = new EnvironmentInfo(ClosureEnvironment(), liftedVars);
            }

            if (IsScopeExpression && parent != null) {
                // scopes share closure IL locals from their containing lambda
                _closureAccess = parent._closureAccess;
            } else {
                // lambdas get their own locals
                _closureAccess = new Dictionary<EnvironmentInfo, Slot>();
            }

            DumpScope();
        }

        [Conditional("DEBUG")]
        private void DumpScope() {
            if (!ScriptDomainManager.Options.ShowScopes) {
                return;
            }
            System.IO.TextWriter output = Console.Out;
#if !SILVERLIGHT
            ConsoleColor color = Console.ForegroundColor;
            try {
                if (Console.BackgroundColor == ConsoleColor.White) {
                    Console.ForegroundColor = ConsoleColor.DarkCyan;
                } else {
                    Console.ForegroundColor = ConsoleColor.Cyan;
                }
#endif
                output.WriteLine("scope {0}({1}):", GetName(_expression), (_parent != null) ? GetName(_parent.Expression) : "");
                if (_localVars.Count > 0) {
                    output.WriteLine("  locals {0}:", _localVars.Count);
                    foreach (Expression v in _localVars) {
                        output.WriteLine("    {0}", CompilerHelpers.GetVariableName(v));
                    }
                }
                if (_environment != null) {
                    output.WriteLine("  lifted {0}:", _environment.Variables.Count);
                    foreach (Expression v in _environment.Variables) {
                        output.WriteLine("    {0}", CompilerHelpers.GetVariableName(v));
                    }
                }
#if !SILVERLIGHT
            } finally {
                Console.ForegroundColor = color;
            }
#endif
        }

        /// <summary>
        /// The lambda or scope expression associated with this scope
        /// </summary>
        internal Expression Expression {
            get { return _expression; }
        }

        /// <summary>
        /// Indicates that this scope closes over variables in a parent scope
        /// </summary>
        internal bool IsClosure {
            get { return _isClosure; }
        }

        /// <summary>
        /// Indicates that this scope has lifted variables
        /// 
        /// These are either closed over from a parent scope, or lifted so we
        /// can provide access via the Expression.LocalVariables() intrinsic.
        /// (TODO: the latter part is not implemented yet)
        /// </summary>
        internal bool HasEnvironment {
            get { return _environment != null; }
        }

        internal bool HasParent {
            get {
                return _parent != null;
            }
        }

        /// <summary>
        /// If this scope represents an inner generator, this will return the outer
        /// generator scope. Otherwise, returns null
        /// </summary>
        internal ScopeInfo GeneratorOuterScope {
            get {
                if (_expression.NodeType == ExpressionType.Generator && _parent != null && _parent.Expression == _expression) {
                    return _parent;
                }
                return null;
            }
        }

        /// <summary>
        /// Called when entering the scope. Performs all variable allocation
        /// needed, including creating environments and IL locals for accessing
        /// parent environments
        /// </summary>
        internal void Enter(LambdaCompiler cg) {
            Debug.Assert(_expression.NodeType != ExpressionType.Generator || cg.IsGeneratorBody == (GeneratorOuterScope != null));

            EmitClosureAccess(cg);
            EmitCreateEnvironment(cg);
            AllocateLocals(cg);
        }

        /// <summary>
        /// Called when exiting the scope. Clears out slots for IL locals.
        /// </summary>
        internal void Exit() {
            _localSlots.Clear();
            if (IsScopeExpression) {
                if (_environment != null) {
                    _closureAccess.Remove(_environment);
                }
            } else {
                _closureAccess.Clear();
            }
        }

        /// <summary>
        /// Emit the nearest environment, or null is there isn't one
        /// </summary>
        internal void EmitNearestEnvironment(LambdaCompiler cg) {
            EnvironmentInfo env = NearestEnvironment();
            if (env != null) {
                _closureAccess[env].EmitGet(cg.IL);
            } else {
                cg.IL.EmitNull();
            }
        }

        #region LocalScopeExpression support

        internal void EmitVariableAccess(LambdaCompiler cg, ReadOnlyCollection<Expression> vars) {
            EnvironmentInfo nearestEnv = NearestEnvironment();
            if (nearestEnv != null) {
                // Find what environment each variable is on & its index
                List<string> names = new List<string>(vars.Count);
                List<long> indexes = new List<long>(vars.Count);

                foreach (Expression variable in vars) {
                    // For each variable, find what environment it's defined on
                    ulong parents = 0;
                    EnvironmentInfo env = nearestEnv;
                    while (env != null && !env.DefinesVariable(variable)) {
                        parents++;
                        env = env.Parent;
                    }
                    
                    if (env != null) {
                        // combine the number of parents we walked, with the
                        // real index of variable to get the index to emit.
                        ulong index = (parents << 32) | (uint)env.GetVariableIndex(variable);

                        names.Add(CompilerHelpers.GetVariableName(variable));
                        indexes.Add((long)index);
                    }
                }

                if (names.Count > 0) {
                    _closureAccess[nearestEnv].EmitGet(cg.IL);
                    cg.EmitConstantArray(names);
                    cg.EmitConstantArray(indexes);
                    cg.IL.EmitCall(typeof(RuntimeHelpers).GetMethod("CreateVariableAccess"));
                    return;
                }
            }

            // No visible variables
            cg.IL.EmitCall(typeof(RuntimeHelpers).GetMethod("CreateEmptyVariableAccess"));
            return;
        }

        #endregion

        #region variable resolution

        /// <summary>
        /// Resolve a local variable in this scope or a closed over scope
        /// Throws if the variable is defined
        /// </summary>
        internal Slot ResolveVariable(Expression variable) {
           
            // Search locals, but only in this lambda
            for (ScopeInfo s = this; s != null; s = s._parent) {
                Slot slot;
                if (s._localSlots.TryGetValue(variable, out slot)) {
                    return slot;
                }

                // if this is a lambda or generator, we're done
                if (!s.IsScopeExpression) {
                    break;
                }
            }

            // search environments
            for (EnvironmentInfo env = NearestEnvironment(); env != null; env = env.Parent) {
                if (env.DefinesVariable(variable)) {
                    return env.GetElementSlot(_closureAccess[env], variable);
                }
            }

            throw new InvalidOperationException(
                string.Format(
                    "variable '{0}' of type '{1}' is not defined in scope '{2}'",
                    CompilerHelpers.GetVariableName(variable),
                    variable.Type,
                    GetName(_expression)
                )
            );
        }

        #endregion

        // private methods:

        private bool IsScopeExpression {
            get { return _expression.NodeType == ExpressionType.Scope; }
        }

        // Lifts IL arguments to the environment, if they are closed over
        private void LiftArguments(LambdaCompiler cg, Slot env) {
            int i = 0;
            foreach (ParameterExpression p in cg.Parameters) {
                if (_environment.DefinesVariable(p)) {
                    _environment.GetElementSlot(env, p).EmitSet(cg.IL, cg.GetLogicalArgument(i));
                }
                i++;
            }
        }

        // Emits creation of the environment storage
        private void EmitCreateEnvironment(LambdaCompiler cg) {
            if (_environment != null) {

                Slot parentSlot = null;
                EnvironmentInfo parent = _environment.Parent;
                if (parent != null) {
                    parentSlot = _closureAccess[parent];
                }

                Slot envSlot = _environment.EmitCreate(cg.IL, parentSlot);

                // If this scope is inside a geneartor and contains a yield, we
                // need to store our environment on the generator's environment
                if (_scopeHasYield) {
                    Slot liftedSlot = cg.NextGeneratorTemp(envSlot.Type);
                    liftedSlot.EmitSet(cg.IL, envSlot);
                    envSlot = liftedSlot;
                }

                _closureAccess.Add(_environment, envSlot);

                if (!IsScopeExpression) {
                    LiftArguments(cg, envSlot);
                }
            }
        }

        // Creates IL locals for accessing closures
        private void EmitClosureAccess(LambdaCompiler cg) {
            if (!IsScopeExpression) {
                Debug.Assert(_closureAccess.Count == 0);

                EnvironmentInfo env = ClosureEnvironment();
                if (env != null) {

                    LocalSlot envSlot = EnvironmentInfo.EmitFromClosureArgument(cg);
                    _closureAccess.Add(env, envSlot);

                    while (env.Parent != null) {
                        envSlot = cg.IL.EmitSetLocal(env.GetParentSlot(envSlot));
                        env = env.Parent;

                        _closureAccess.Add(env, envSlot);
                    }
                }
            }
        }

        // Gets the current environment, or the closed over environment
        private EnvironmentInfo NearestEnvironment() {
            return _environment ?? ClosureEnvironment();
        }

        // Gets the closed over environment
        private EnvironmentInfo ClosureEnvironment() {
            EnvironmentInfo env = null;
            ScopeInfo s = this;
            while (s != null && s._isClosure && env == null) {
                s = s._parent;
                env = s._environment;
            }
            return env;
        }

        // Allocates slots for IL locals or IL arguments
        private void AllocateLocals(LambdaCompiler cg) {
            // allocate slots for non-lifted variables
            foreach (Expression v in _localVars) {
                Slot s;
                if (v.NodeType == ExpressionType.Parameter) {
                    s = cg.GetLogicalArgument((ParameterExpression)v);
                } else {
                    s = cg.GetNamedLocal(v.Type, CompilerHelpers.GetVariableName(v));
                }
                _localSlots.Add(v, s);
            }
        }

        #region static helper methods

        // Gets the name of the LambdaExpression or ScopeExpression
        internal static string GetName(Expression scope) {
            Assert.NotNull(scope);

            switch (scope.NodeType) {
                case ExpressionType.Scope:
                    return ((ScopeExpression)scope).Name;
                case ExpressionType.Lambda:
                case ExpressionType.Generator:
                    return ((LambdaExpression)scope).Name;
                default: throw Assert.Unreachable;
            }
        }

        #endregion

    }
}
